#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 215. 数组中的第K个最大元素.py
@time: 2022/1/5 13:59
@desc:
    - 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
      请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    - https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
@解题思路：
    1. 快排到中枢的位置是k-1
    2. 注意是逆序
    3. 随机快排
    4. Ot(n), Os(logn)
'''
import random
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def k_quick_sort(nums, low, high, k):
            def pivot(nums, low, high):
                piv = nums[low]
                while low<high:
                    while low<high and nums[high]<=piv: high -= 1
                    # 找到后半区间大于中枢的则前移
                    nums[low] = nums[high]
                    while low<high and nums[low]>=piv: low += 1
                    # 找到前半区间小于中枢的则后移
                    nums[high] = nums[low]
                    # ---- 至此完成了一次逆序的修正 ---
                # 当low==high时，所有比piv小的都到了右半区间，大的都到了左半区间
                nums[low] = piv
                return low
            if low<high:
                idx = pivot(nums, low, high)
                if idx == k-1:
                    return
                else:
                    k_quick_sort(nums, low, idx-1, k)
                    k_quick_sort(nums, idx+1, high, k)
        # 快排直到当前pivot的索引是k-1
        k_quick_sort(nums, 0, len(nums)-1, k)
        return nums[k-1]

# 随机快排
class Solution2(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """

        def pivot(nums, low, high):
            idx = random.randint(low, high)
            nums[idx], nums[low] = nums[low], nums[idx]
            piv = nums[low]
            while low < high:
                while low < high and nums[high] <= piv: high -= 1
                nums[low] = nums[high]
                while low < high and nums[low] >= piv: low += 1
                nums[high] = nums[low]
            nums[low] = piv
            return low

        def k_quick_sort(nums, low, high):
            if low >= high: return
            piv = pivot(nums, low, high)
            if piv == k - 1: return
            k_quick_sort(nums, low, piv - 1)
            k_quick_sort(nums, piv + 1, high)

        k_quick_sort(nums, 0, len(nums) - 1)
        return nums[k - 1]

if __name__ == '__main__':
    inp = [3,2,1,5,6,4]
    k = 2
    res = Solution().findKthLargest(inp, k)
    print(res)
